package com.fanwh.sort.BubbleSort;

/**
 * @program: DataStructure
 * @description: 优化冒泡排序
 * @author: Fanwh
 * @create: 2020-09-23 18:02
 **/


import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**1、为什么要优化冒泡排序？
 * 答：当在进行冒泡排序的过程中，出现数组顺序已经有序（在某一趟排序中，没有发生一次交换），
 *      但是计算机并不知道这一点，还会继续运行，导致资源的浪费
 *2、如何优化冒泡排序算法？
 * 答：当出现在某一趟排序中，没有发生一次交换的情况时，我们可以提前结束冒泡排序。
 *      是否提前结束通过采用标志位flag进行判断。
 */

public class OptimizeBubbleSort {

    public int[] OptimizeBubbleSort(int[] a){
        int temp = 0;//临时变量
        boolean flag = false;//标识变量，表示是否进行过交换；
        for (int i = 0; i < a.length-1; i++) {
            for (int j = 0; j < a.length-1-i; j++) {
                if(a[j] > a[j+1]){
                    flag = true;
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
            if(flag == false){//在一趟排序中，没有发生一次交换
                System.out.println("在第"+(i+1)+"趟提前结束了");
                break;//提前结束冒泡排序
            }else {
                flag = false;//重置flag,进行下一次判断
            }
        }
        return a;
    }

    public static void main(String[] args) {

        int[] arr = {3,9,-1,10,-2};
        OptimizeBubbleSort optimizeBubbleSort = new OptimizeBubbleSort();
        int[] arrsort = optimizeBubbleSort.OptimizeBubbleSort(arr);
        System.out.println(Arrays.toString(arrsort));

        /*//测试冒泡排序的速度，其时间复杂度为O(n^2)
        int[] arr = new int[80000];//给80000个数据进行测试
        for (int i = 0; i <arr.length ; i++) {
            arr[i] = (int)(Math.random()*80000);//生成一个[0,80000)的数；
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String datestr1 = simpleDateFormat.format(date1);
        System.out.println("排序之前的时间："+datestr1);

        OptimizeBubbleSort optimizeBubbleSort = new OptimizeBubbleSort();
        optimizeBubbleSort.OptimizeBubbleSort(arr);
        Date date2 = new Date();
        String datestr2 = simpleDateFormat.format(date2);
        System.out.println("排序之后的时间："+datestr2);*/
    }
}
